Математические основы защиты информации и информационной безопасности
Леонтьева К. А., НПМмд-02-23
Российский университет дружбы народов
Москва, Россия
14 октября 2023
Целое число d ≠ 0 называется наибольшим общим делителем целых чисел a1, a2, ..., ak (обозначается d= НОД (a1,a2,...,ak)), если выполняются следующие условия:
каждое из чисел a1, a2, ..., ak делится на d,
если d1 ≠ 0 - другой общий делитель чисел a1, a2, ..., ak, то d делится на d1.
Для вычисления наибольшего общего делителя двух целых чисел применяется способ повторного деления с остатком, называемый алгоритмом Евклида.
Бинарный алгоритм Евклида основан на следующих свойствах наибольшего общего делителя (считаем, что 0 < b ≤ a):
если оба числа a и b четные, то НОД(a,b) = 2* НОД$(\frac {a}{2}, \frac{b}{2})$
если число a - нечетное, число b -четное, то НОД(a,b)= НОД$(a, \frac{b}{2})$
если оба числа a и b нечетные, a > b, то НОД(a,b)= НОД(a−b,b)
если a = b, то НОД(a,b) = a